/*
** file : data_lnk.c
** date : 02/26/04
*/
#include <stdlib.h>
#include <string.h>


void* talloc(long siz)
{
    return calloc(((siz+15)/16)*16, 1);
}

void tfree(void *p)
{
    free(p);
}


//
//  single link list structs. it is assumed the first
//  sizeof(void*) bytes are used as pointer to the
//  next element
//
void *nxtlink_add(void *elm, void *anchor)
{
    if( 0 == anchor )
    {
        *(void**)elm = 0;

        // this is the first element
        return elm;
    }

    // insert at head
    *(void**)elm = anchor;

    return elm; 
}

//
//  single link list structs. it is assumed the first
//  sizeof(void*) bytes are used as pointer to the
//  next element
//
void *nxtlink_att(void *elm, void *anchor)
{
    void *nod;

    *(void**)elm = 0; // no next

    if( 0 == anchor )
    {
        // this is the first element
        return elm;
    }

    // search to last element
    for(nod = anchor; *(void**)nod; nod = *(void**)nod );

    //attach at tail
    *(void**)nod =  elm;

    return anchor; // same anchor
}

// 
// delete an element, return anchor
//
void *nxtlink_del(void *elm, void *anchor)
{
    void *e;

    if( 0 == elm || 0 == anchor )
    {
        return 0; // nothing to remove
    }

    if( elm == anchor)
    {
        return *(void**)elm;  
    }

    for( e = anchor; *(void**)e; e = *(void**)e )
    {
        // if 'elm' follows 'e'
        if( *(void**)e == elm )
        {
            *(void**)e = *(void**)elm; // transit

            break;
        }
    }

    return anchor; 
}


//
// seach through a link list. the key is defined as
// size and offset into the element's structure
//
void* nxtlink_get(void *key, int ksz, int koff, void *anchor)
{
    void *e;

    if( 0 == anchor )
    {
        return 0;  // empty link list
    }

    for(e = anchor; e; e = *(void**)e )
    {
        if( ksz > 0 )
        {
            if( 0 == memcmp(key, (char*)e + koff, ksz) )
            {
                // found!
                break;
            }
        }
        else
        {
            // character string 
            if( 0 == strcmp(key, (char*)e + koff) )
            {
                break;
            }
        }
    }

    return e;
}

//
// walk thru link list.
// 1. if 'item' is null, return the first element
// 2. if 'item' is in the list, return its next
// 3. if 'itme' is not found, return null.
//
void* nxtlink_nxt(void *item, void *anchor)
{
    void *e;

    if( 0 == item )
    {
        return anchor;  // first element
    }

    for( e = anchor; e; e = *(void**)e )
    {
        if( item == e )
        {
            return *(void**)e;
        }
    }

    return 0;  // item is anchor or not found
}

/////////////////////////////////////////////////////////////////////////////

#include "data_lnk.h"
//
// double link functions
//


// add an item to tail of list
void dll_add_tail(dll_t* item, dlh_t* anchor)
{
    if( item == 0 || anchor == 0 ) return;

    item->prev = anchor->tail;

    item->next = 0;   // last item in list

    if( anchor->tail )
    {
        anchor->tail->next = item;
    }

    anchor->tail = item;


    if( 0 == anchor->head )
    {
        anchor->head = item;  // dll was empty
    }
}

// add an item to head of list
void dll_add_head(dll_t* item, dlh_t* anchor)
{
    if( item == 0 || anchor == 0 ) return;

    item->prev = 0;  // first item in list

    item->next = anchor->head;

    if( anchor->head )
    {
        anchor->head->prev = item;
    }
    
    anchor->head = item; 

    if( 0 == anchor->tail )
    {
        anchor->tail = item; // dll was empty
    }
}

// delete an item from dll
void dll_del_item(dll_t* item, dlh_t* anchor)
{
    dll_t *p, *n;

    if( 0 == item || 0 == anchor ) return;

    if( (p = item->prev) )
    {
        p->next = item->next;
    }

    if( (n = item->next) )
    {
        n->prev = p;
    }

    if( anchor->tail == item )
    {
        // this was tail in list
        anchor->tail = p;
    }

    if( anchor->head == item )
    {
        // this was head in list
        anchor->head = n;
    }
}

// serach dll by comparing a key to a block in dll item
dll_t* dll_key_search(void *key, int size, int offset, dlh_t* anchor)
{
    dll_t *e; 

    for( e = anchor->head; e; e = e->next )
    {
        if( 0 == memcmp(key, (char*)e + offset, size) )
        {
            return e;
        }
    }

    return 0;
}

// update dll header fields
void dll_sync(dlh_t* anchor)
{
    dll_t *e;

    // for now the only to sync number of items
    anchor->length = 0;

    for(e = anchor->head; e; e = e->next )
    {
        anchor->length += 1;
    }
}
